package com.easy.carl.algorithm.array.matrix;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName SpiralOrder54
 * @Description 54. 螺旋矩阵
 * @Author zheng
 * @Date 2021/12/16 14:20
 * @Version 1.0
 **/
public class SpiralOrder54 {
    public List<Integer> spiralOrder(int[][] matrix) {
        //结果
        List<Integer> res = new ArrayList<>();
        //行、列
        int row = matrix.length;
        int col = matrix[0].length;
        //开始的行列索引
        int startRow = 0, startCol = 0;
        //偏移量
        int offset = 1;
        //总个数
        int total = row * col;

        int loop = Math.min(row, col) / 2;

        while (loop > 0) {
            int tmpStartRow = startRow;
            int tmpStartCol = startCol;
            //横向遍历，从左至右，左闭右开
            for (; tmpStartCol < col - offset; tmpStartCol++) {
                res.add(matrix[tmpStartRow][tmpStartCol]);
            }
            //竖向遍历 从上至下，上闭下开
            for (; tmpStartRow < row - offset; tmpStartRow++) {
                res.add(matrix[tmpStartRow][tmpStartCol]);
            }
            //横向遍历 从右至左，右闭左开
            for (; tmpStartCol >= offset; tmpStartCol--) {
                res.add(matrix[tmpStartRow][tmpStartCol]);
            }
            //竖向遍历，从下至上，下闭上开
            for (; tmpStartRow >= offset; tmpStartRow--) {
                res.add(matrix[tmpStartRow][tmpStartCol]);
            }
            offset++;
            startRow++;
            startCol++;
            loop--;
        }
        //遍历结束，数组中长度小于总个数，说明有未加入的数据
        if (res.size() < total) {
            //行比列多，行数据存在未遍历的，否则，列存在未遍历的
            if (row > col) {
                for (; startRow <= row - offset + 1 && res.size() < total; startRow++) {
                    res.add(matrix[startRow][startCol]);
                }
            } else {
                for (; startCol <= col - offset + 1 && res.size() < total; startCol++) {
                    res.add(matrix[startRow][startCol]);
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        SpiralOrder54 spiralOrder54 = new SpiralOrder54();
        System.out.println(spiralOrder54.spiralOrder(new int[][]{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}).toString());
    }
}
